// 实现一个稳定的计数排序，基于桶排序思想

function countSort(nums: number[]): number[] {
    // 求最大最小值来处理计数区间
    const min: number = Math.min(...nums);
    const max: number = Math.max(...nums);
    // 初始化桶和结果数组
    const budget = new Array(max - min + 1).fill(0);
    const res = new Array(nums.length); // 结果数组
    // 对分桶来计数
    for (let i = 0; i < nums.length; i++) {
        budget[nums[i] - min]++;
    }
    // 计算累加数组，注意是对桶累加
    for (let i = 1; i < budget.length; i++) {
        budget[i] = budget[i] + budget[i - 1];
    }
    // 进行计数排序
    for (let i = nums.length - 1; i >= 0; i--) {
        // 先求出原始值，然后根据桶的计数来计算原始值在结果数组中的位置
        if (budget[nums[i] - min] > 0) {
            budget[nums[i] - min]--;
            res[budget[nums[i] - min]] = nums[i];
        }
    }
    return res;
}


// 桶排序测试用例函数
function budgetTestUnits(minValue: number, maxValue: number, arrCount: number, testCount: number) {
    for (let i = 0; i < testCount; i++) {
        const instance: number[] = [];
        for (let i = 0; i < arrCount; i++) {
            instance[i] = Math.floor(Math.random() * (maxValue - minValue) + 1) + minValue;
        }
        console.log(`排序前：${instance} , 排序后：${countSort(instance)}`);
    }
}

// 单元测试，在1-15之间，数组长度为10，测试5组
budgetTestUnits(1, 15, 10, 5)